The present invention relates to a fast Fourier transform operation device and method thereof, and more particularly relates to a fast Fourier transform operation device and method thereof capable of higher speeds.
Recently, digitization has become widespread in broadcast technology. FIG. 1 shows an example configuration of a receiving device for DAB (Digital Audio Broadcasting) that is one way of putting audio signals into digital form and then broadcasting digital radio broadcasts. Here, a tuner 102 received signals for a prescribed broadcast station (channel) from a signal received via an antenna 101 and outputs these signals to an A/D converter 103. The A/D converter 103 then converts the inputted signal from analog to digital. A "fast Fourier transform" (hereinafter abbreviated to "FFT") circuit 104 then performs FFT operations to convert from data on a time axis inputted by the A/D converter 103 to data for a plurality of sub-carrier waves on a frequency axis. This FFT circuit 104 is supplied with a symbol component after guard interval components provided between neighboring symbols on the time axis have been removed.
A de-interleaving and error correction circuit 105 performs de-interleaving and error correction processing on the output of the FFT circuit 104. Part of the signal that has been processed by the de-interleaving and error correction circuit 105 is then supplied to a decoder 106. This signal is then DQPSK (Differential Quadrature Phase Shift Keying) demodulated, with a left channel audio signal and a right channel audio signal then being outputted from speakers 107 and 108, respectively. An appended data output circuit 109 then separates and outputs appended data such as program contents and traffic information from the signal outputted by the de-interleaving and error correction circuit 105.
FIG. 2 shows an example configuration of this kind of related FFT circuit 104. In this example, inputted data is inputted to an input terminal in0 or in1 of a butterfly operator 4 via a selector 2 and a selector 3 after being temporarily stored in an input buffer 1. The butterfly operator 4 is an operator that perform butterfly operations (two point DFTs (Discrete Fourier Transforms)) of, for example, radix 2, reads rotational operator data (rotational factor) stored in a ROM 5 (Read Only Memory) as appropriate, performs butterfly operations on data inputted from terminal in0 and in1, and outputs this data to terminal out0 and out1.
The selector 6 selects data outputted from the terminals out0 and out1 of the butterfly operator 4 and outputs this data to a selector 7. The selector 7 then outputs data inputted from the selector 6 to a memory 8 or an output buffer 9. The memory 8 stores data inputted by the selector 7, reads this data at a prescribed timing and supplies this data to the selector 2.
The selector 2 selects the output from the input buffer 1 until all of the data comprising the processing unit for the butterfly operation have been selected from the input buffer 1. Then, after all of the data that is to undergo butterfly operations has been inputted from the input buffer 1, the data inputted from the memory 8 is selected and outputted to the selector 3. The process for executing the butterfly operation is then repeated a prescribed number of times on the results of the butterfly operation from the butterfly operator 4.
For example, as shown in the timing chart in FIG. 3, when the data 0 (butterfly operation results) from the terminal out0 of the butterfly operator 4 and the data 1 (butterfly operation results) from the terminal out1 are respectively outputted, the selector 6 operates on a clock that a period that is 1/2 (twice the frequency) of the period for the output of the butterfly operator 4. As a result, the data 0 outputted by the terminal out0 is selected in the first half of the period for the output of the butterfly operator and the data 1 outputted by the terminal out1 is selected in the second half of this period. The data 0 and the data 1 is therefore selected by the selector 7, supplied to the memory 8 and written, i.e. the two butterfly operation results outputted simultaneously by the butterfly operator 4 are converted from parallel to serial at the selector 6 and supplied to and stored in the memory 8 via the selector 7. The data stored in the memory 8 is then read-out again and supplied to terminals in0 and in1 of the butterfly operator 4 via the selectors 2 and 3.
Namely, as shown in FIG. 3, reading and writing of data to and from the memory 8 is carried out in 1/2 a period of the cycle for changing over the selector 6. For example, when the data 0 is outputted by the selector 6, the data 0 is written to the memory 8 in the first half of this period and the data already stored in the memory 8 is read-out in the second half of this period. This data is then inputted to, for example, terminal in0 of the butterfly operator 4 via the selectors 2 and 3.
Data 1 is written to the memory 8 in the first half of the period of the selector 6 outputting the data 1 and prescribed data already stored in the memory 8 is read out in the following half and is supplied to, for example, terminal in1 of the butterfly operator 4 via the selectors 2 and 3.
The same process is then repeatedly executed thereafter.
With this related FFT operation device (in this case, the FFT circuit 104), as shown in FIG. 3, when the frequency of the operating clock of the butterfly operator 4 is taken to be 1, the frequency of the operating clock for the memory 8 has to be four times this frequency. In other words, when the operating clock of the memory 8 is decided, the operation occurring at the butterfly operator 4 has to be carried out at a speed that is 1/4 of that of this clock. However, the butterfly operator 4 can operate at a higher speed than this and the maximum processing capabilities are not fulfilled, with this being one reason that hampers making of the FFT operation high-speed.
As the present invention sets out to resolve the aforementioned problems, it is the object of the present invention to carry out operations at a higher speed.